6.26 测试

6.26 测试

混氏新子 蒟蒻
  2023-07-01 21:05:48 2023-07-01 21:05:48 创建   2023-09-24 19:11:36 2023-09-24 19:11:36 更新    2.4k 字  12 分钟  

前情提要

题目描述

成绩表

成绩表

出师不利啊，第一题爆零了。

题解

T1

#贪心

正解是贪心，我用 DP （也许是递推，分不太清）， 我没有考虑到翻了之后可以不走的情况，可以先把负数的 a 直接赋值为，这样也会更方便想，到时候排序一下要翻的，前 m 个就行。

正解代码：

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define N 100010
using namespace std;
using ll = long long;
int n, m;
ll a[N], p[N];
int prp[N];
vector <ll> v[2];
ll ans[2];
int main() {
	freopen("ctrl.in", "r", stdin);
	freopen("ctrl.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		scanf("%lld", a + i);
		if (a[i] < 0) a[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		scanf("%lld", p + i);
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", prp + i);
		v[prp[i] ^ 1].emplace_back(max(-p[i], a[i] - p[i]));
		v[prp[i]].emplace_back(- a[i] - p[i]);
	}
	sort(v[0].begin(), v[0].end(), greater<ll>());
	sort(v[1].begin(), v[1].end(), greater<ll>());
	for (int i = 0; i < n; ++i) {
		if (a[i] > 0) {
			ans[prp[i]] += a[i];
		}
	}
	for (int i = 0; i < m && v[0][i] > 0 && i < v[0].size(); ++i) {
		ans[0] += v[0][i];
	}
	for (int i = 0; i < m && v[1][i] > 0 && i < v[1].size(); ++i) {
		ans[1] += v[1][i];
	}
	printf("%lld", max(ans[0], ans[1]));
	return 0;
}

T2

#模拟

75 分， GG again

黑白相间，提供增加2、3、4个作用，可以证明能够加出所有的情况，除了1或者最大值 - 1都是行的。这道题当时没想出正解，但是也朝这个方向想过，2 、 3 、4 个的作用，但是不知道为啥没搞出来。悲催。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
int t, n, m;
int his[25];
bool flag;
void dfs(int step, int tot) {
	if (flag) return;
	if (tot > m || tot + (n - step) * ((n << 1) - 1) < m) return;
	if (step == n) {
		if (tot == m) {
			flag = 1;
			puts("Possible");
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					printf("%d", (his[i] >> j) & 1);
				}
				puts("");
			}
		}
		return;
	}
	for (int i = 0; i < (1 << n); ++i) {
		int tmp = 0;
		for (int j = 0; j < n - 1; ++j) {
			if (((i >> j) & 1) ^ ((i >> (j + 1)) & 1)) ++tmp;
		}
		if (step) tmp += __builtin_popcount(i ^ his[step - 1]);
		his[step] = i;
		dfs(step + 1, tot + tmp);
	}
}
int main() {
	freopen("genshin.in", "r", stdin);
	freopen("genshin.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		if (m == 1 || m == n * (n - 1) * 2 - 1) {
			puts("Impossible");
			continue;
		} else if(m <= n) {
			puts("Possible");
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= n; ++j) {
					if (i == 1 && j < m) {
						printf("1");
					} else {
						printf("0");
					}
				}
				puts("");
			}
			continue;
		}
		if (n <= 20) {
			flag = 0;
			dfs(0, 0);
			if (!flag) {
				puts("Impossible");
			}
		}
		else {
			int n4, n3, n2 = 0, re = m;
			n4 = min(m / 4, ((n - 2) * (n - 2) + 1) / 2);
			re -= n4 * 4;
			if (re == 1) --n4, re += 4;
			n3 = min(re / 3, (n - 2) / 2 * 4);
			re -= n3 * 3;
			if (re & 1) --n3, re += 3;
			n2 = re / 2;
			puts("Possible");
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= n; ++j) {
					if ((i + j) % 2) printf("0");
					else {
						if ((i + j == n + 1 || i == j) && (i == 1 || i == n)) {
							printf("%d", n2 ? 1 : 0);
							if (n2) --n2;
						} else if (i == 1 || j == 1 || i == n || j == n) {
							printf("%d", n3 ? 1 : 0);
							if (n3) --n3;
						} else {
							printf("%d", n4 ? 1 : 0);
							if (n4) --n4;
						}
					}
				}
				puts("");
			}
		}
	}
	return 0;
}

T3

#dp

这道题方法很妙，考场上没想出来，经验不够。

前置知识

(注：这里可以两个式子都没有等于)

然后我们就可以转化式子了！

我们可以轻松发现就是排序后的， 并且显然构成的一个序列是单调的，是。

于是我们就开始做了，先枚举，然后枚举这个序列有前有多少个，然后计算满足这种情况的贡献之和，首先计算这个排列的个数，然后将每个的位置放上可行的数 （满足的条件），乘起来就行，可以证明这样是不会重的。

代码量小，思维量大，需要足够的知识储备和经验。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
using ll = long long;
int n, m;
ll ans;
ll fact[5010], factni[5010];
ll pp[5010][5010];
inline ll qp(ll x, ll y) {
	ll ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % mod;
		y >>= 1;
		x = x * x % mod;
	}
	return ans;
}
inline ll c(int x, int y) {
	return fact[x] * factni[y] % mod * factni[n - y] % mod;
}
int main() {
	freopen("lty.in", "r", stdin);
	freopen("lty.out", "w", stdout);
	scanf("%d%d", &n, &m);
	fact[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fact[i] = fact[i - 1] * i % mod;
		factni[i] = qp(fact[i], mod - 2);
	}
	for (int i = 1; i <= m; ++i) {
		pp[i][0] = 1;
		for (int j = 1; j <= n; ++j) {
			pp[i][j] = pp[i][j - 1] * i % mod;
		}
	}
	for (int j = 1; j <= m; ++j) {
		for (int i = 1; i < n; ++i) {
			ans += pp[j][i] * pp[m - j][n - i] % mod * c(n, i) % mod * min(i, n - i) % mod;
			ans %= mod;
		}
	}
	printf("%lld", ans * 2ll % mod);
	return 0;
}

T4

#凸壳

爆砍 7 分。

这个取反指取相反数，6。

考试时把取反当成将序列反转，而且还给加上了 l 和 r 。 哭死。

显然最后一步（前缀或后缀）对整个序列操作一定是最优的。

可以证明最多3步就行，前缀和最小处和最大处可以分别向后和向前更新得到大于零的。如果最小位在最大位后，做一下1就行了。

然后1步先搞出来，问题在两步时，可以是两个前缀，两个后缀，取反后前后缀（和前后缀后取反一样，易证），先前后后，现后后前。

两次前缀必定是从开头开始最优（后缀同理），而问题在于后两种。我们考虑先前后后，最后一种同理。

可以做出前缀和，前缀和的前缀和，然后表示操作后每一位的值。正解是先枚举 r ，然后找 l ，前和后容易办，问题在中间，正解不太会，直接上图，以后再看。

official solution

但是呢，这个数据可以卡过 （doge，就是先把其它杂七杂八的处理了，然后从前往后找式子中正着找最长的满足是正数的序列，然后再用上面题解那个式子判定，就是的。

正确性：？

预计得分：100?

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>
#define N 200010
#define func
using namespace std;
using ll = long long;
int n, id;
ll a[N], b[N], s[N], sp[N], maxs[N], mins[N];
int x = 1, y = 1, yz, zy;
bool flag;
inline void clamp(ll & val, ll minn, ll maxn) {
	val = min(max(val, minn), maxn);
}
int main() {
	freopen("plan.in", "r", stdin);
	freopen("plan.out", "w", stdout);
	scanf("%d%d", &n, &id);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", a + i);
		if (a[i] < 0) flag = 1;
		s[i] = a[i] + s[i - 1];
		sp[i] = sp[i - 1] + s[i];
		if (i == 1) maxs[i] = s[i];
		else maxs[i] = max(s[i], maxs[i - 1]);
		if (!zy && s[i] < 0) zy = i - 1;
		if (s[i] < s[x]) x = i;
		if (s[i] > s[y]) y = i;
	}
	yz = n;
	for (int i = n; i; --i) {
		if (i == n) mins[i] = s[i];
		else mins[i] = min(s[i], mins[i + 1]);
	}
	while (s[n] - s[yz - 1] >= 0) --yz;
	if (!flag) {
		printf("0");
		return 0;
	}
	ll tmp = 0, tmp1 = 0;
	bool orz = 0;
	for (int i = 1; i <= n; ++i) {
		if (tmp < 0) break;
		tmp += a[i];
	}
	for (int i = n; i; --i) {
		if (tmp1 < 0) break;
		tmp1 += a[i];
	}
	for (int i = 1; i <= n; ++i)
		if (a[i] > 0) orz = 1;
	if (!orz) {
		puts("1\n1");
		return 0;
	} else if (tmp >= 0) {
		printf("1\n2 1 %d\n", n);
		return 0;
	} else if (tmp1 >= 0) {
		printf("1\n3 1 %d\n", n);
		return 0;
	}
	//2qq
	func{
		int p1, i;
		b[0] = 0;
		for (int i = 1; i <= n; ++i) b[i] = a[i];
		for (i = 1; i <= n; ++i) {
			b[i] = a[i];
			b[i] += b[i - 1];
			if (b[i] < 0) break;
		}
		p1 = i;
//		cout << s[75] << s[76] << endl;
		for (i = 1; i <= n; ++i) {
			b[i] += b[i - 1];
			if (b[i] < 0) break;
		}
		if (b[i] >= 0) {
			printf("2\n2 1 %d\n2 1 %d", p1, n);
			return 0;
		}
	}
	//2hh
	func{
		int p1, i;
		for (int i = n; i; --i) b[i] = a[i];
		for (i = n; i; --i) {
			b[i] = a[i];
			b[i] += b[i + 1];
			if (b[i] < 0) break;
		}
		p1 = i;
		for (i = n; i; --i) {
			b[i] += b[i + 1];
			if (b[i] < 0) break;
		}
		if (b[i] >= 0) {
			printf("2\n3 %d %d\n3 1 %d", p1, n, n);
			return 0;
		}
	}
	for (int i = 1; i <= n; ++i) a[i] = -a[i];
	func {
		ll tmp = 0, tmp1 = 0;
		for (int i = 1; i <= n; ++i) {
			if (tmp < 0) break;
			tmp += a[i];
		}
		for (int i = n; i; --i) {
			if (tmp1 < 0) break;
			tmp1 += a[i];
		}
		if (tmp >= 0) {
			printf("2\n1\n2 1 %d\n", n);
			return 0;
		} else if (tmp1 >= 0) {
			printf("2\n1\n3 1 %d\n", n);
			return 0;
		}
	}
	for (int i = 1; i <= n; ++i) a[i] = -a[i];
	if (x < y) {
		printf("2\n2 %d %d\n3 1 %d", x + 1, n, n);
		return 0;
	}
	func{
	int lst = 1, tmp = a[1], mini = 1;
	for (int i = 2; i <= n + 1; ) {
		if (tmp < 0 || i > n) {
			if (i - 1 < yz) goto fail;
			if (s[n] - s[i - 1] + sp[i - 1] - sp[mini - 1] - s[lst - 1] * (i - 1 - mini + 1) < 0) goto fail;
			if (s[n] - s[i - 1] + sp[i - 1] - sp[lst - 1] - s[lst - 1] * (i - 1 - lst + 1) + s[lst - 1] - maxs[lst - 2] < 0) goto fail;
			printf("2\n2 %d %d\n3 1 %d", lst, i - 1, n);
			return 0;
			fail:;
			while (i <= n && a[i] < 0) ++i;
			if (i > n) break;
			lst = i;
			tmp = a[i];
			mini = i;
			++i;
		}
		if (s[lst - 1] * i - sp[i - 1] < s[lst - 1] * mini - sp[mini - 1]) mini = i;
		tmp += a[i];
		++i;
	}
	}
	func{
	int lst = n, tmp = a[n], mini = n;
	for (int i = n - 1; ~i; ) {
		if (tmp < 0 || !i) {
			if (i + 1 > zy) goto fail2;
			if (s[i] + s[lst] * (mini - i) - sp[mini - 1] + sp[i - 1] < 0) goto fail2;
			if (s[i] + s[lst] * (lst - i) - sp[lst - 1] + sp[i - 1] + mins[lst + 1] - s[lst] < 0) goto fail2;
			printf("2\n3 %d %d\n2 1 %d", i + 1, lst, n);
			return 0;
			fail2:;
			while (i > 0 && a[i] < 0) --i;
			if (!i) break;
			lst = i;
			tmp = a[i];
			mini = i;
			--i;
		}
		if (s[lst] * i - sp[i - 1] < s[lst] * mini - sp[mini - 1]) mini = i;
		tmp += a[i];
		--i;
	}
	}
	
	printf("3\n1\n2 %d %d\n3 1 %d", min(x, y) + 1, n, n);
	return 0;
}

P.S. 上面那个代码写得跟屎一样，慎读。

后记

第一天，不太好。有志者，事竟成。

  • 标题: 6.26 测试
  • 作者: 混氏新子
  • 创建于 : 2023-07-01 21:05:48
  • 更新于 : 2023-09-24 19:11:36
  • 链接: https://blog.huasushis.cn/2023/6.26 测试/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 7.4 测试 7.4 测试 2023年11月2日总结 2023年11月2日总结
推荐阅读
6.29 测试 6.29 测试 7.4 测试 7.4 测试
评论
此页目录
6.26 测试
  1. 前情提要
    1. 成绩表
  2. 题解
    1. T1
    2. T2
    3. T3
      1. 前置知识
    4. T4
  3. 后记